package com.shm.leetcode;

import javafx.scene.transform.Rotate;

import java.util.*;

/**
 * @author: shm
 * @dateTime: 2020/10/27 8:26
 * @description: 144. 二叉树的前序遍历
 * 给定一个二叉树，返回它的 前序 遍历。
 *
 *  示例:
 *
 * 输入: [1,null,2,3]
 *    1
 *     \
 *      2
 *     /
 *    3
 *
 * 输出: [1,2,3]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class PreorderTraversal {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }

    public List<Integer> preorderTraversal_2(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty()||node!=null){
            while (node!=null){
                ans.add(node.val);
                stack.push(node);
                node=node.left;
            }
            node = stack.pop();
            node=node.right;
        }
        return ans;
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/27 9:05
     * @description: 迭代解法
     * 本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。
     *
     * 前序遍历
     * 首先我们应该创建一个Stack用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。
     *
     * 之后我们应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。
     * 此时你能得到的流程如下:
     *
     * 作者：gre-z
     * 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
     */
    public List<Integer> preorderTraversal_3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root==null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(node);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            list.add(pop.val);
            if (pop.right!=null){
                stack.push(node.right);
            }
            if (pop.left!=null){
                stack.push(node.left);
            }
        }
        return list;
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/27 9:28
     * @description: Morris解法
     * Morris遍历使用二叉树节点中大量指向null的指针，由Joseph Morris 于1979年发明。
     * 时间复杂度：O(n)O(n)
     * 额外空间复杂度：O(1)O(1)
     *
     * 在你阅读以下代码之前，在这边先讲解一下Morris的通用解法过程。
     *
     * Morris的整体思路就是将 <u>以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接</u>
     * 我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。
     * 在某个根结点创建连线的时候打印。因为我们是顺着左边的根节点来创建连线，且创建的过程只有一次。
     * 打印某些自身无法创建连线的节点，也就是叶子节点。
     *
     * 作者：gre-z
     * 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
     */
    public List<Integer> preorderTraversal_4(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root==null){
            return ans;
        }
        //当前开始遍历的节点
        TreeNode cur1 = root;
        //记录当前结点的左子树
        TreeNode cur2 = null;
        while (cur1!=null){
            cur2 = cur1.left;
            if (cur2!=null) {
                //找到当前左子树的最右侧节点，且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                //这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
                if (cur2.right == null) {
                    cur2.right = cur1;
                    ans.add(cur1.val);
                    cur1 = cur1.left;
                    continue;
                } else {
                    //当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，
                    // 同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点 了，把路断开。
                    cur2.right = null;
                }
            }else {
                ans.add(cur1.val);
            }
            //一直往右边走，参考图
            cur1=cur1.right;
        }
        return ans;
    }
}
